#!/usr/bin/python
# -*- coding: utf8 -*-

import sys
import os
import array

from grammar import *


# take grammar as parameter
def inside(g):
    nodes_len = len(g.nodes)
    links_len = len(g.links)

    probs = array.array('d', [0 for i in range(0, nodes_len)])
    for i in range(0, nodes_len):
        node = g.nodes[i]
        if node_l(node) == node_r(node):
            index = node_l(node)
            t = g.types[index]
            probs[i] = get_terminal_rule((node_s(node), t)).prob
    for i in range(0, links_len):
        s, x, y, r = g.links[i]
        probs[s] += probs[x] * probs[y] * get_rule(r).prob

    return probs
        

def outside(g, inside_probs):
    nodes_len = len(g.nodes)
    links_len = len(g.links)

    probs = array.array('d', [0 for i in range(0, nodes_len)])
    start = get_symbol('START').index
    for i in range(0, nodes_len):
        if node_s(g.nodes[i]) == start:
            probs[i] = 1
    # in reverse order for outside algorithm
    for i in range(nodes_len - 1, -1, -1):
        s, x, y, r = g.links[i]
        prob[x] += prob[s] * inside_prob[y] * get_rule(r).prob
        prob[y] += prob[s] * inside_prob[x] * get_rule(r).prob
    return probs


def viterbi():
    return None




if __name__ == '__main__':
    print "faint"
